#include <iostream>
#include <fstream>
#include <sstream>

#include <string>
#include <vector>
#include <map>

#include <limits>

#include <queue>

class Vertex;
struct Edge;

typedef std::map<int, int> mapii;
typedef std::map<int, Vertex *> mapiv;

enum State { Unvisited, Visited };


struct Vertex {
	/*Vertex(std::string strName) : name(strName), edges(std::vector<Edge*>()) {}
	std::string name;*/
	Vertex(int nId) : id(nId), state(Unvisited), edges(std::vector<Edge*>()) {}
	int id;
	State state;
	std::vector<Edge*> edges; 	//combined with Edge.indexA and Edge.indexB
};					// this provides O(1) lookup


struct Edge {
	Edge(Vertex* vA, Vertex* vB, int d) 
	: a(vA), b(vB), indexA(0), indexB(0), dist(d) {}
	
	Vertex *a;
	Vertex *b;
	int indexA;
	int indexB;
	int dist;
};

struct Graph {
  std::vector<Edge*> E;
  std::map<int, Vertex*> V;
  
  ~Graph() {
    for(int i=0; i<E.size(); i++) {
      delete E[i];
    }
    
    for(int i=0; i<V.size(); i++) {
      std::map<int, Vertex*>::iterator it;
      for(it=V.begin(); it!=V.end(); ++it) {
	Vertex *v = it->second;
	//delete v;
      }
    }
  }
  
  Vertex* addVertex(int id)
  {
    Vertex *pA;
    if (V.find(id) == V.end()) {
      pA = new Vertex(id);
      V.insert(std::make_pair(id, pA));
    }
    else {
      pA = V[id];
    }
    return pA;
  }

  Vertex* addEdge(int a, int b, int dist) {
    // create vertices
    Vertex *pA = addVertex(a);
    Vertex *pB = addVertex(b);
    
    // create edge in graph
    Edge *pE = new Edge(pA, pB, dist);
    E.push_back(pE);
    
    // add to vertex a
    pA->edges.push_back(pE);
    pE->indexA = pA->edges.size() - 1;
    
    // add to vertex b
    pB->edges.push_back(pE);
    pE->indexB = pB->edges.size() - 1;
  }
  
  void printEdges() {
    //std::cout << "Edges: " << E.size() << ", Vertices: " << V.size() << std::endl;
    
    for(int i=0; i<E.size(); i++) {
      std::cout << E[i]->a->id << "," << E[i]->b->id << ": " << E[i]->dist << std::endl;
    }
  }
  
  void printVertices() {
    //std::cout << "Edges: " << E.size() << ", Vertices: " << V.size() << std::endl;
    mapiv::iterator it;
    
    for(it=V.begin(); it!=V.end(); ++it) {
      
      std::cout << it->second->id << ":";
      
      for(int j=0; j < it->second->edges.size(); j++) {
	Edge *e = it->second->edges[j];
	std::cout << "(" << e->a->id << "," << e->b->id << ": " << e->dist << ") ";
      } 
      
      std::cout << std::endl;
    }
  }

  void dfs()
  {
    std::queue<int> Q;
    
    mapiv::iterator it;
    it=V.begin();
    if (it == V.end())
      return;
    
    Q.push(it->first);  
    it->second->state = Visited;
    
    while(!Q.empty()) {
      int v = Q.front();
      Q.pop();
      std::cout << v << " ";
      
      for(int j=0; j < V[v]->edges.size(); j++) {
	Edge *pEdgeVW = V[v]->edges[j];
	
	Vertex *pW;
	if (v == pEdgeVW->a->id)
	  pW = pEdgeVW->b;
	else
	  pW = pEdgeVW->a;
      
	if(pW->state == Unvisited) {
	  Q.push(pW->id);
	  pW->state = Visited;
	}
      } 
    }
    
    std::cout << std::endl;
    
  }
};




int main(int argc, char*argv[])
{
    std::ifstream input_file;
    int v1, v2, dist;
    std::string line;
    
    std::cout << "Reading file" << argv[1] << std::endl;
    
    Graph G;
    
    input_file.open(argv[1]);
    if (input_file.is_open())
    {
      while(std::getline(input_file, line))
      {
	std::istringstream iss(line);
	if(iss >> v1 >> v2 >> dist) {
	  //std::cout << v1 << " " << v2 << " " << dist << std::endl;
	  
	  // create vertices in graph	  
	  G.addEdge(v1, v2, dist);
	}
      }
    }
    
    input_file.close();
    G.dfs();
    
    //G.printEdges();
    //G.printVertices();
    
    
    
    return 0;
}
